package 左哥算法.ch06二叉树;

import org.junit.Test;

public class Ch07搜索二叉树 {

    /****************以下是BST的测试用例****************/
    @Test
    public void addAndFindTest(){
        SearchTree<Integer> root = new SearchTree<>(8);
        root.add(10);
        root.add(4);
        root.add(6);
        root.add(7);
        System.out.println(root.find(11));  //查找离该值最近的节点
    }

    @Test
    public void removeTest(){
        SearchTree<Integer> root = new SearchTree<>(20);
        root.add(30);
        root.add(15);
        root.add(10);
        root.add(5);
        root.add(12);
        root.add(11);
        root.add(18);
        root.add(19);
        root.remove(15);    //删除孩子双全的节点
        root.remove(18);    //删除孩子不全的节点
        root = root.remove(20);//删除叶子节点
        root=root.remove(30);    //删除叶子节点
        System.out.println();
    }

    @Test
    public void spinTest(){
        SearchTree<Integer> root=new SearchTree<>(10);
        root.add(15);
        root.add(5);
        root.add(3);
        root.add(7);
        root=root.rightSpin();  //自行断点测试
        root=root.leftSpin();
        System.out.println();
    }

    /****************以下是AVL的测试用例****************/

    @Test
    public void AVLTreeTest(){
        SearchTree<Integer> root=new AVLTree<>(20);
        root=root.add(30);
        root=root.add(10);
        root=root.add(40);
        root=root.add(8);
        root=root.add(15);
        root=root.add(16);
        root=root.add(17);
        root=root.add(18);
        System.out.println();
    }

    @Test
    public void AVL_LL(){
//        SearchTree<Integer> root=new AVLTree<>(50);
//        root = root.add(70);
//        root = root.add(30);
//        root = root.add(40);
//        root = root.add(20);
//        root = root.add(10);    //LL

        SearchTree<Integer> root=new AVLTree<>(100);
        root = root.add(50);
        root = root.add(150);
        root = root.add(30);
        root = root.add(20);
        System.out.println();
    }

    @Test
    public void AVL_LR(){
        SearchTree<Integer> root=new AVLTree<>(50);
        root = root.add(70);
        root = root.add(30);
        root = root.add(20);
        root = root.add(40);
        root = root.add(45);
        System.out.println();
    }

    @Test
    public void AVL_RR(){
        SearchTree<Integer> root=new AVLTree<>(50);
        root = root.add(70);
        root = root.add(30);
        root = root.add(80);
        root=root.remove(30);
        System.out.println();
    }

    @Test
    public void AVL_RL(){
        SearchTree<Integer> root=new AVLTree<>(50);
        root = root.add(70);
        root = root.add(30);
        root = root.add(60);
        root=root.remove(30);
        System.out.println();
    }


    /****************以下是Size Balance Tree的测试用例****************/
    @Test
    public void SBT_LL(){
        SearchTree<Integer> root=new SizeBalanceTree<>(50);
        root=root.add(30);
        root=root.add(70);
        root=root.add(15);
        root=root.add(40);
        root=root.add(10);
        System.out.println();
    }

    @Test
    public void SBT_LR(){
        SearchTree<Integer> root=new SizeBalanceTree<>(50);
        root=root.add(30);
        root=root.add(70);
        root=root.add(15);
        root=root.add(40);
        root=root.add(45);
        System.out.println();
    }

    @Test
    public void SBT_RR(){
        SearchTree<Integer> root=new SizeBalanceTree<>(50);
        root=root.add(30);
        root=root.add(70);
        root=root.add(90);
        root=root.remove(30);
        System.out.println();
    }

    @Test
    public void SBT_RL(){
        SearchTree<Integer> root=new SizeBalanceTree<>(50);
        root=root.add(30);
        root=root.add(70);
        root=root.add(60);
        System.out.println();
        root=root.remove(30);
        System.out.println();
    }

    @Test
    public void test(){

        TreeNode root = new TreeNode(78);
        root.right=new TreeNode(31);
        root.right.right=new TreeNode(22);
        root.right.right.right=new TreeNode(4);
        root.right.right.right.right=new TreeNode(82);
        root.right.right.right.right.right=new TreeNode(35);
        root.right.right.right.right.right.right=new TreeNode(112);
        root.right.right.right.right.right.right.right=new TreeNode(128);

        AVLTree2 myfun=new AVLTree2();
        TreeNode treeNode = myfun.balanceBST(root);
        Answer test=new Answer();
        TreeNode newRoot = test.balanceBST(root);
        System.out.println();
    }

    @Test
    public void test02(){
        SearchTree<Integer> root=new AVLTree<>(78);
        root=root.add(31);
        root=root.add(22);
        root=root.add(4);
        root=root.add(82);
        root=root.add(35);
        root=root.add(112);
        root=root.add(128);
        System.out.println();
    }
}